# coding: UTF-8

import random
import copy

SPACE = 0
MARU = 1
BATSU = -1
MARKS = (" ", "O", "X")

class Cell(object):
    def __init__(self):
        self.value = SPACE
    
    def set(self, value):
        self.value = value
    
    def getmark(self):
        return MARKS[self.value]
    
    def is_empty(self):
        return self.value == SPACE

LINES = ((0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6), (1, 4, 7), (2, 5, 8), (0, 4, 8), (2, 4, 6))
VALUES = (MARU, BATSU)

class Board(object):
    def __init__(self):
        self.cells = [Cell() for i in range(9)]
    
    def display(self):
        print("+---+---+---+")
        cell_line = "|"
        for i in range(9):
            cell_line += " " + self.cells[i].getmark() + " |"
            if i % 3 == 2:
                print(cell_line)
                cell_line = "|"
                print("+---+---+---+")
    
    def is_empty(self, index):
        return self.cells[index].is_empty()
    
    def count(self):
        count = 0
        for current in self.cells:
            if not current.is_empty():
                count += 1
        return count
    
    def winner(self):
        return MARKS[VALUES[(self.count() + 1) % 2]]
    
    def current_turn(self):
        return VALUES[self.count() % 2]
    
    def put(self, index):
        self.cells[index].set(self.current_turn())
    
    def is_lined(self):
        for current in LINES:
            total = 0
            for i in current:
                total += self.cells[i].value
                if abs(total) == 3:
                    return True
        return False
    
    def __is_filled(self):
        return self.count() > 8
    
    def is_finished(self):
        return self.__is_filled() or self.is_lined()
    
    def empties(self):
        return [index for index, value in enumerate(self.cells) if value.is_empty()]
    
    def reaches(self):
        return self.__reaches(1)
    
    def counter_reaches(self):
        return self.__reaches(-1)
    
    def __reaches(self, be):
        return [l for l in LINES if self.__line_total(l) * self.current_turn() == 2 * be]
    
    def __line_total(self, targets):
        total = 0
        for index in targets:
            total += self.cells[index].value
        return total
    
    def empty_in_reaches(self, reaches):
        for index in random.choice(reaches):
            if self.cells[index].is_empty():
                return index
    
    def empty_in_reach(self, reach):
        for index in reach:
            if self.cells[index].is_empty():
                return index

def human(board):
    while True:
        row = input("Rows? : ")
        if row not in(1,2,3):
            print("Input 1, 2 or 3.")
            continue
        
        column = input("Column? : ")
        if column not in(1,2,3):
            print("Input 1, 2 or 3.")
            continue
        
        return (row - 1) * 3 + (column - 1)

def computer_random(board):
    return random.choice(board.empties())

def computer_medium(board):
    if board.reaches():
        return board.empty_in_reaches(board.reaches())
    elif board.counter_reaches():
        return board.empty_in_reaches(board.counter_reaches())
    else:
        for candidate in board.empties():               # 空いているマスでループ
            simulator = copy.deepcopy(board)            # コピー
            simulator.put(candidate)                    # 置いてみる
            if len(simulator.counter_reaches()) > 1:    # ダブルリーチかどうか確認
                return candidate
        for candidate in board.empties():                   # 空いているマスでループ
            simulator = copy.deepcopy(board)                # コピー
            simulator.put(candidate)                        # 置いてみる
            for one_liner in simulator.counter_reaches():                   # リーチのラインでループ
                next_simulator = copy.deepcopy(simulator)                   # コピー
                next_candidate = next_simulator.empty_in_reach(one_liner)   # リーチを止める
                next_simulator.put(next_candidate)
                if len(next_simulator.counter_reaches()) < 2:               # ダブルリーチかどうか確認
                    return candidate
        return computer_random(board)

CORNERS = [0, 2, 6, 8]
CENTER = 4

def merge_pop(list1, list2):        # 2 つのリストをマージしてランダム選択
    return random.choice(list(set(list1) & set(list2)))

def random_corner(board):           # 角のいずれか
    return merge_pop(board.empties(), CORNERS)

def random_center_corner(board):    # 真ん中か角のいずれか
    return merge_pop(board.empties(), CORNERS + [CENTER])

def is_center_empty(board):         # 真ん中が空いているかチェック
    return CENTER in board.empties()

def is_corners_all_empty(board):    # 角がすべて空いているかチェック
    return [cell for cell in board.empties() if cell in CORNERS]

def near_corner(board):             # 近くの角でリーチがかけられるマス
    first = set(CORNERS) - set(board.empties())
    opposite = CORNERS[-1 - CORNERS.index(list(first)[0])]
    nears = set(CORNERS) - first - set([opposite])
    for corner in nears:
        simulator = copy.deepcopy(board)
        simulator.put(corner)
        if simulator.counter_reaches():
            return corner

def opposite_corner(board):         # 対角のマス
    first = set(CORNERS) - set(board.empties())
    return CORNERS[-1 - CORNERS.index(list(first)[0])]

def computer_strong(board):
    if board.count() == 0:
        return random_center_corner(board)
    elif board.count() == 1:
        if is_center_empty(board):
            return CENTER
        else:
            return random_corner(board)
    elif board.count() == 2:
        if board.cells[CENTER].value == board.current_turn():
            if is_corners_all_empty(board):
                return random_corner(board)
            else:
                return near_corner(board)
        else:
            if is_center_empty(board):
                return near_corner(board)
            else:
                return opposite_corner(board)
    else:
        return computer_medium(board)

PLAYER_NAMES = ('Human', 'Weak CPU', 'Nornal CPU', 'Strong CPU')
PLAYER_FUNCS = (human, computer_random, computer_medium, computer_strong)

def choose_player(name):
    print(name + "?")
    print(player_msg())
    return input()

def player_msg():
    msg = ""
    for i, v in enumerate(PLAYER_NAMES):
        msg += "   " + str(i) + ":" + v
    return msg

if __name__ == '__main__':
    players = [PLAYER_FUNCS[choose_player(name)] for name in ("1st", "2nd")]
    board = Board()
    while not board.is_finished():
        target_index = players[board.count() % 2](board)
        if board.is_empty(target_index):
            board.put(target_index)
        else:
            print("Not empty. Try another.")
            continue
        board.display()
    
    if board.is_lined():
        print("Game over. " + board.winner() + " won.")
    else:
        print("Game over. Draw.")
